A semaphore is a variable in a location in system memory, and indicates the availability of a resource shared by multiple processes in a computer system. Typically, each shared resource has its own semaphore. There are two main types of semaphores: counting semaphores and binary semaphores. A counting semaphore, the value of which can vary between zero and a predetermined positive number that represents the number of processes that can access the shared resource at the same time, is used when more than one process can access the shared resource at the same time. A binary semaphore, however, is used when only one process at a time can access the shared resource. Accordingly, a binary semaphore has only two values, one to show that a process is using the shared resource, and the other to show that no process is using the shared resource.
In order to access a shared resource using a binary semaphore, a process first reads the binary semaphore. If the current value of the binary semaphore indicates that the shared resource is not available, the process can do one of two things. The process can either abandon attempts to access the shared resource, or begin “spinning,” i.e., periodically re-reading the binary semaphore until the shared resource becomes available. Conversely, if the process reads the binary semaphore and the current value indicates that the shared resource is available, the process writes to the binary semaphore a value indicating to other processes that the shared resource is not available, and accesses the shared resource. When finished using the shared resource, the process releases it by writing to the binary semaphore a value indicating that the shared resource is available. If another process has been spinning, the read executed after the shared resource becomes available will reveal to the spinning process that the shared resource is available. The spinning process can then write to the binary semaphore a value indicating to other processes that the shared resource is not available and access the shared resource, as explained previously.
The sequence of reading a binary semaphore, determining that a shared resource is available, writing to the binary semaphore a value indicating to other processes that the shared resource is not available, and accessing the shared resource, is known as “read modify write” (RMW) access. RMW access must be “atomic,” i.e., continuous without interference, during the period between reading the binary semaphore when the shared resource is available, and writing to the binary semaphore a value indicating to other processes that the shared resource is not available. If an RMW by a first process is not atomic, then a second process can execute a separate read on the binary semaphore after the first process' read but prior to the first process' write. That is, if the first process does not write to the binary semaphore prior to the second process' read a value indicating that the shared resource is not available, the second process determines that the shared resource is available. Consequently, both the first process and the second process can write to the binary semaphore values indicating to other processes that the shared resource is not available. Each process will therefore believe it has exclusive access to the shared resource, thus resulting in a collision of accesses.
A process can use a “bus lock” to restrict access to a binary semaphore, thereby preventing another process from executing a read during an in-progress RMW, and eliminating the possibility of a collision of accesses to the shared resource. With a bus lock, a process, prior to reading the binary semaphore, locks the bus that provides access to the binary semaphore. The process then attempts RMW access, after which the bus is automatically unlocked. Finally, the process determines whether it was able to write to the binary semaphore a value indicating to other processes that the shared resource is not available. If so, then the shared resource was available at the time of the read, and thus the process can access the shared resource. If not, then the shared resource was not available at the time of the read, and the process cannot access the shared resource.
Though preventing an intervening read during an in-progress RMW, a bus lock can be implemented to restrict access to all semaphores, not just the semaphore subject to the RMW, until the RMW is complete. Furthermore, because semaphores are located in system memory, in some implementations a bus lock might prevent all processes, including those not attempting to read a semaphore, from accessing system memory. In addition, some computer systems do not have bus lock capability. These systems therefore use highly complex algorithms to provide atomic access to semaphores, which reduces system performance.